﻿using System;
using System.Collections.Generic;
using static xsb.core.Data;

namespace xsb.core
{
    class Algorithms
    {
        public static List<Group> run_once(int group_count, int factor)
        {
            List<Group> groups = create_empty_groups(group_count);

            //男生分配部分
            {
                List<Person> pool_male = gen_pool_gender(true);
                disorder_once(ref pool_male);

                /*
                 * 种子选手的分配
                 * 从所有人的池中移除种子选手
                 * 并将其平摊到各组
                 * */
                {
                    //抽取种子选手
                    List<Person> seeds = new List<Person>();
                    for (int i = 0; i < pool_male.Count; i++)
                    {
                        if (pool_male[i].seed)
                        {
                            seeds.Add(pool_male[i]);
                            pool_male.RemoveAt(i);
                            i--;
                        }
                    }

                    //平摊分配种子选手
                    int index = 0;
                    foreach (Person person in seeds)
                    {
                        groups[index].addMember(person);
                        if (++index == groups.Count)
                        {
                            index = 0;
                        }
                    }
                }

                /*
                 * 分配普通人
                 */
                {
                    //把每个人分配到可能是最合适的组里
                    foreach (Person person in pool_male)
                        best_group_college(groups, person).addMember(person);
                }
            }

            //女生分配部分
            {
                List<Person> pool_female = gen_pool_gender(false);
                disorder_once(ref pool_female);
                /*
                 * 首先是种子选手
                 * 遵守的分配逻辑：
                 * 尽量摊开
                 * 不允许摊到有自己学院种子选手的组上
                 * 当然，如果人数失衡可以后期通过migration调整
                 */

                //抽取种子选手
                List<Person> seeds = new List<Person>();
                for (int i = 0; i < pool_female.Count; i++)
                {
                    if (pool_female[i].seed)
                    {
                        seeds.Add(pool_female[i]);
                        pool_female.RemoveAt(i);
                        i--;
                    }
                }

                //平摊分配种子选手

                //排序一下以确保种子选手少的组会优先得到女生种子选手
                sort_groups_by_seed_num(ref groups);

                int index = 0;
                foreach (Person person in seeds)
                {
                    groups[index].addMember(person);
                    if (++index == groups.Count)
                    {
                        index = 0;
                    }
                }

                /*
                 * 接下来是普通人
                 * 最好是分配到只有男生且没有同学院的组里
                 * 但是情况不一定理想
                 * 可能需要在 有非同学院女生 和 同学院男生 之间选择
                 * 通过一个权值来为各组创建一个分数，根据分数选择最佳组
                 */

                //为各组创建分数，但是这个分数是对于每个人而言的，这就很坏
                int rank_have_same_college = factor;
                int rank_have_female = 10 - factor;
                foreach(Person person in pool_female)
                {
                    //创建分数
                    foreach(Group group in groups)
                    {
                        group.rank = 0;
                        group.rank += rank_have_same_college * group.getCountOfTargetCollege(person.college);
                        group.rank += rank_have_female * group.female_num;
                    }

                    best_group_rank(groups).addMember(person);
                }

            }

            {
                //但是，上面的这一切并不能确保人数是均衡的，因此需要额外的手动平衡
                //尽可能利用那些“没什么影响”的分配
                double average = (double)all_person.Count / group_count;
                for (int i = 0; i < group_count; i++)
                {
                    for (int j = 0; j < group_count; j++)
                    {
                        if (i == j)
                            continue;

                        //对任意两个组进行比较，将其压向平均值
                        //这两个组必须一个大于平均值，一个小于平均值
                        bool can_start = groups[i].members.Count - average > 0;
                        bool can_end = groups[j].members.Count - average < 0;
                        if (can_start && can_end)
                            try_fair_migration(groups[i], groups[j], average);

                    }
                }
            }

            return groups;
        }

        /*
         * 根据性别排列，男生在前，女生在后
         * 没法ref 强迫症难受
         */
        static void sort_person_by_gender(List<Person> group)
        {
            for (int i = 0; i < group.Count - 1; i++)
            {
                for (int j = i + 1; j < group.Count; j++)
                {
                    if (group[j].is_male && !group[i].is_male)
                    {
                        Person tmp = group[i];
                        group[i] = group[j];
                        group[j] = tmp;
                    }
                }
            }
        }

        /*
         * 根据rank值，寻找最佳组
         */
        static Group best_group_rank(List<Group> groups)
        {
            Group target = null;
            int min = Int32.MaxValue;

            foreach(Group group in groups)
            {
                if (group.rank < min)
                {
                    min = group.rank;
                    target = group;
                }
            }

            return target;
        }

        /*
         * 根据种子选手人数，对各组进行重新排序
         */
        static void sort_groups_by_seed_num(ref List<Group> groups)
        {
            for(int i = 0; i < groups.Count - 1; i++)
            {
                for (int j = i + 1; j < groups.Count; j++)
                {
                    if (groups[j].getSeedNum() < groups[i].getSeedNum())
                    {
                        Group tmp = groups[i];
                        groups[i] = groups[j];
                        groups[j] = tmp;
                    }
                }
            }
        }

        /*
         * 生成对应性别的“所有人池”
         */
        static List<Person> gen_pool_gender(bool is_male)
        {
            List<Person> ret = new List<Person>();
            foreach(Person person in all_person)
            {
                if (person.is_male == is_male)
                    ret.Add(person);
            }

            return ret;
        }

        /*
         * 尝试将普通人从start迁往end
         * 此方法不会影响人数均衡
         * 
         * 比如从某学院在A组有2人B组有1人
         * 到B组2人A组1人
         * 没有实际区别
         * 
         * 此处传的是引用，但是语法上不支持ref一个list成员
         * 虽然没啥影响 但强迫症无奈了
         */
        static void try_fair_migration(Group start, Group end, double average)
        {
            //让键值成为一个list
            List<string> keys = new List<string>();

            foreach(string key in start.college_num.Keys)
            {
                keys.Add(key);
            }

            //每一个学院
            for(int i=0;i<keys.Count;i++)
            {
                if (start.members.Count <= average || end.members.Count >= average)
                    return;

                if (start.getCountOfTargetCollege(keys[i]) > end.getCountOfTargetCollege(keys[i]))
                {
                    //确认了某个学院的人可以被转移
                    //上面的算法已经决定了start最多比end多一人，因此无需多虑
                    //开始转移成员
                    Person victim = lock_victim_of_target_college(start, keys[i], end);
                    if (victim == null)
                        continue;

                    end.addMember(victim);
                    start.removeMember(victim);
                    i--;
                }
            }
        }

        /*
         * 从某个组中挑出一个指定学院的人
         */
        static Person lock_victim_of_target_college(Group group, string college, Group dest)
        {
            //把男生丢到前面，确保首先被转移的不是女生
            sort_person_by_gender(group.members);

            foreach(Person person in group.members)
                //允许随意调度普通人
                //仅在公平的前提下调度种子选手
                //不允许在两组种子选手人数相同时调度种子选手（造成不均）
                if(person.college == college 
                    && (!person.seed || person.seed && group.getSeedNum() > 1 && group.getSeedNum() != dest.getSeedNum()))
                    return person;

            return null;
        }

        /*
         * 返回同学院人数最少的目标组引用
         */
        static Group best_group_college(List<Group> groups, Person person)
        {
            Group target = null;
            int min = Int32.MaxValue;
            string college = person.college;

            for(int i = 0; i < groups.Count; i++)
            {
                if (groups[i].getCountOfTargetCollege(college) < min)
                {
                    min = groups[i].getCountOfTargetCollege(college);
                    target = groups[i];
                }
            }

            return target;
        }

        static List<Group> create_empty_groups(int count)
        {
            List<Group> ret = new List<Group>();
            while (count-- != 0)
            {
                ret.Add(new Group());
            }
            return ret;
        }

        //保障在连续调用时仍然有一定的随机性
        static int random_seed;
        static void disorder_once<T>(ref List<T> target)
        {
            List<T> ret = new List<T>();
            
            Random random = new Random(DateTime.UtcNow.Millisecond + random_seed++);

            while (target.Count>0)
            {
                int victim = random.Next(target.Count);
                ret.Add(target[victim]);
                target.RemoveAt(victim);
            }

            target = ret;
        }
    }
}
